import java.util.LinkedList;

/*
 * @lc app=leetcode.cn id=21 lang=java
 *
 * [21] 合并两个有序链表
 */

// @lc code=start
// class ListNode {
//       int val;
//       ListNode next;
//       ListNode() {}
//       ListNode(int val) { this.val = val; }
//       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//   }
 
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        LinkedList<ListNode> data=new LinkedList<>();
        while(list1!=null||list2!=null){
            if (list1==null) {
                data.addLast(list2);
                list2=list2.next;
                continue;
            }
            if (list2==null) {
                data.addLast(list1);
                list1=list1.next;
                continue;
            }
            if (list1.val<list2.val) {
                data.addLast(list1);
                list1=list1.next;
                continue;
            }
            else{
                data.addLast(list2);
                list2=list2.next;
                continue;
            }            
        }
        for (ListNode listNode : data) {
            listNode.next=null;
        }
        ListNode res=data.pollFirst();
        ListNode middle=res;
        while (!data.isEmpty()) {
            middle.next=data.pollFirst();
            middle=middle.next;
        }
        return res;
    }
}
// @lc code=end

